package com.bo.sort;

import java.util.Arrays;

/**
 * 基于比较排序总结
 *
 * @Author: gpb
 * @Date: 2023/12/20 11:26
 * @Description:
 */
public class Sort {

    public static void main (String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] testArr1 = generateRandomArray(maxSize, maxValue);
            int[] testArr2 = copyArray(testArr1);
            int[] testArr3 = copyArray(testArr1);
            int[] testArr4 = copyArray(testArr1);
            int[] testArr5 = copyArray(testArr1);
            int[] testArr6 = copyArray(testArr1);
            insertionSort(testArr1);
            selectionSort(testArr2);
            bubbleSort(testArr3);
            mergeSort(testArr4);
            quickSort(testArr5);
            heapSort(testArr6);
            if (!isEqual(testArr1, testArr2) || !isEqual(testArr1, testArr3) || !isEqual(testArr1, testArr4) || !isEqual(testArr1, testArr5) || !isEqual(testArr1, testArr6)) {
                System.out.println("出错了！");
                System.out.println("testArr1: " + Arrays.toString(testArr1));
                System.out.println("testArr2: " + Arrays.toString(testArr2));
                System.out.println("testArr3: " + Arrays.toString(testArr3));
                System.out.println("testArr4: " + Arrays.toString(testArr4));
                System.out.println("testArr5: " + Arrays.toString(testArr5));
                System.out.println("testArr6: " + Arrays.toString(testArr6));
                break;
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 插入排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 无稳定性
     * @param arr
     */
    public static void insertionSort (int[] arr) {
        try {
            arrIsNull(arr);
        } catch (Exception e) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j + 1, j);
                }
            }
        }
    }

    /**
     * 选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 有稳定性
     * @param arr
     */
    public static void selectionSort (int[] arr) {
        try {
            arrIsNull(arr);
        } catch (Exception e) {
            return;
        }
        // 0 ~ N-1  找到最小值，在哪，放到0位置上
        // 1 ~ n-1  找到最小值，在哪，放到1 位置上
        // 2 ~ n-1  找到最小值，在哪，放到2 位置上
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            swap(arr, min, i);
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 有稳定性
     * @param arr
     */
    public static void bubbleSort (int[] arr) {
        try {
            arrIsNull(arr);
        } catch (Exception e) {
            return;
        }
        // 0 ~ N-1
        // 0 ~ N-2
        // 0 ~ N-3
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 有稳定性
     * @param arr
     */
    public static void mergeSort (int[] arr) {
        if (arr == null || arr.length < 2) {
            // 插入排序一下
            insertionSort(arr);
            return;
        }
        processMergeSort(arr, 0, arr.length - 1);
    }

    /**
     * 归并排序
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void processMergeSort (int[] arr, int l, int r) {
        // 终止条件
        if (l == r) {
            return;
        }
        // 中点
        int mid = l + ((r - l) >> 1);
        // 左部分
        processMergeSort(arr, l, mid);
        // 右部分
        processMergeSort(arr, mid + 1, r);
        // 合并
        mergeSortToMerge(arr, l, mid, r);
    }

    /**
     * 归并排序合并
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void mergeSortToMerge (int[] arr, int l, int mid, int r) {
        // 辅助数组
        int[] help = new int[r - l + 1];
        // 左指针开始位置
        int p1 = l;
        // 右指针开始位置
        int p2 = mid + 1;
        // 辅助数组指针
        int i = 0;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 复制剩余的数据,要么p1指针没执行完成,要么p2指针没有完成
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        // 回填数组
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    /**
     * 快排
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(logN)
     * 无稳定性
     * @param arr
     */
    public static void quickSort (int[] arr) {
        if (arr == null || arr.length < 2) {
            // 插入排序一下
            insertionSort(arr);
            return;
        }
        processQuickSort(arr, 0, arr.length - 1);
    }

    private static void processQuickSort (int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        // 快速排序,选择的数要随机性
        swap(arr, r, l + (int) (Math.random() * (r - l + 1)));
        // 荷兰国旗问题
        int[] partition = partition(arr, l, r);
        // l-partition[0]-1 左部分
        processQuickSort(arr, l, partition[0] - 1);
        // partition[1]+1~r 右部分
        processQuickSort(arr, partition[1] + 1, r);
    }

    public static int[] partition (int[] arr, int l, int r) {
        if (l > r) {
            return new int[]{-1, -1};
        }
        if (l == r) {
            return new int[]{l, r};
        }
        int less = l - 1;
        int index = l;
        int more = r;
        while (index < more) {
            if (arr[index] < arr[r]) {
                swap(arr, index++, ++less);
            } else if (arr[index] > arr[r]) {
                swap(arr, index, --more);
            } else {
                index++;
            }
        }
        // arr[r]位置和大于指针进行交换
        swap(arr, r, more);
        // 返回 中间相等访问数组下标
        return new int[]{less + 1, more};
    }


    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 无稳定性
     * @param arr
     */
    public static void heapSort (int[] arr) {
        if (arr == null || arr.length < 2) {
            // 插入排序一下
            insertionSort(arr);
            return;
        }
        // 把数组维护成堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        heapSize--;
        // 把最大元素移动到数组最后
        for (int i = 0; i < heapSize; heapSize--) {
            swap(arr, 0, heapSize);
            // 维护堆
            heapIfy(arr, 0, heapSize);
        }
    }

    /**
     * 把元素添加到堆里面去
     * 需要和父节点进行比较
     * 父节点的位置：(i-1)-2
     *
     * @param arr
     * @param i
     */
    public static void heapInsert (int[] arr, int i) {
        while (arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    /**
     * 维护堆
     * 需要index位置的下沉,如果index位置的小于他的左孩子或者右孩子
     * 进行下沉
     * 左孩子
     * i*2+1
     * 右孩子
     * i*2+2
     *
     * @param arr
     * @param index
     */
    public static void heapIfy (int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            // 找出最大的孩子下标
            int ans = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 看看最大孩子是否大于当前位置的数
            ans = arr[index] > arr[ans] ? index : ans;
            if (ans == index) {
                return;
            }
            swap(arr, index, ans);
            index = ans;
            left = index * 2 + 1;
        }
    }


    public static void arrIsNull (int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new NullPointerException("数组为空");
        }
    }

    public static void swap (int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // for test
    public static int[] generateRandomArray (int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray (int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual (int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray (int[] arr) {
        if (arr == null) {
            return;
        }
        System.out.println(Arrays.toString(arr));
    }

}
